package com.mlick.a.huweiod;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * 任务 混部
 * 题目描述
 * 公司创新实验室正在研究如何最小化资源成本，最大化资源利用率，请你设计算法帮他们解决一个任务混部问题：
 * 有 taskNum 项任务，每个任务有开始时间（startTime），结束时间（endTime），并行度(parallelism)三个属性，
 * 并行度是指这个任务运行时将会占用的服务器数量，一个服务器在每个时刻可以被任意任务使用但最多被一个任务占用，任务运行完会立即释放（结束时刻不占用）。
 * 任务混部问题是指给定一批任务，让这批任务由同一批服务器承载运行，请你计算完成这批任务混部最少需要多少服务器，从而最大化控制资源成本。 输入描述
 * 第一行输入为 taskNum，表示有 taskNum 项任务
 * 接下来 taskNum 行，每行三个整数，表示每个任务的开始时间（startTime
 * ），结束时间（endTime），并行度(parallelism)
 * 输出描述
 * 一个整数，表示最少需要的服务器数量
 * <p>
 * <a href="https://blog.csdn.net/qfc_128220/article/details/128192516">...</a>
 */
public class H1 {


    // 解题思路: https://www.bilibili.com/video/BV1nq4y1B7Mm/?vd_source=b5105a99a0628dd906e154263279c518
    // 首先，将所有区间按开始位置升序
    // 然后，遍历排序后区间，并将小顶堆中小于遍历区间起始位置的区间弹出（小顶堆实际存储区间结束位置），
    // 此操作后，小顶堆中剩余的区间个数，就是和当前遍历区间重叠数。
    //
    // 最大区间重叠个数
    // 但是本题并不是要求解最大区间重叠个数，而是要求解重叠区间的权重和。
    // 因此，我们需要定义一个变量sum来记录重叠区间的权重和，
    // 当小顶堆弹出不重叠区间时，sum需要减去被弹出区间的权重，当
    // 我们向小顶堆压入重叠区间时，则sum需要加上被压入区间的权重。

    static class Solution {
        public int cal(int[][] ss) {

            // 根据左侧第一个进行排序
            Arrays.sort(ss, Comparator.comparingInt(a -> a[0]));

            // 维护一个小顶推,
            PriorityQueue<Integer[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));

            int sum = 0, max = 0;
            for (int[] range : ss) {
                int s = range[0];
                int e = range[1];
                int p = range[2];

                while (pq.size() > 0) {
                    Integer[] top = pq.peek();
                    if (top[0] > s) {
                        break;
                    }

                    Integer[] poll = pq.poll();
                    sum -= poll[1];
                }

                pq.add(new Integer[]{e, p});
                sum += p;

                max = Math.max(sum, max);
            }

            return max;
        }
    }


    // 差分数列求解
    // https://fcqian.blog.csdn.net/article/details/128976936
    // 当我们要给区间的某个范围的每个元素加上相同的增量时，
    // 此时最简单的方法就是先求解对应区间的差分数列，然后在差分数列对应范围的左右边界上做处理
    static class Solution2 {
        public int cal(int[][] ss) {


            // 构造差分数列
            int[] arr = new int[50000];
            for (int[] range : ss) {
                int s = range[0];
                int e = range[1];
                int p = range[2];

                arr[s] += p;
                // 结束时刻不占用，因此不需要end+1
                arr[e] -= p;
            }

            int ans = arr[0];

            // 求解差分数列的前缀和
            for (int i = 1; i < arr.length; i++) {
                arr[i] += arr[i - 1];
                ans = Math.max(ans, arr[i]);
            }

            return ans;
        }
    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();

        int[][] ss = new int[n][3];

        for (int i = 0; i < n; i++) {
            ss[i][0] = scanner.nextInt();
            ss[i][1] = scanner.nextInt();
            if (ss[i][0] > ss[i][1]) {
                System.err.println("value exception");
                System.exit(-1);
            }

            ss[i][2] = scanner.nextInt();
        }

        System.out.println(new Solution().cal(ss));
        System.out.println(new Solution2().cal(ss));
    }


}
